﻿/*  Copyright (c) 2012 William Rogers and James Boud

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using JBBRXG11ContentFBXModel;

namespace JBBRXG11//JBBRXG11ContentPipeline
{
    class JBBRXG11ModelAdjacency
    {
        struct adjacencyreport
        {
            public int coincidentline, vertexnotonedge, noadjacency, doublefilled;
            public int totalerror { get { return coincidentline + vertexnotonedge + noadjacency + doublefilled; } }
            public adjacencyreport(int junk)
            {
                vertexnotonedge = noadjacency = coincidentline = doublefilled = 0;
            }
            public override string ToString()
            {
                return "Adj report: Coincident lines = " + coincidentline.ToString() + ", Vertex not on edge = " + vertexnotonedge.ToString() +
                                 ", Missing adjacency = " + noadjacency.ToString() + ", Double adjacency = " + doublefilled.ToString();
            }
        }

        struct edge
        {
            public int other, adj, link;  // -1 tag for free or extends into overflow area of array, so may be bigger than ushort max
            public override string ToString() { return other.ToString() + " " + adj.ToString() + " " + link.ToString(); }
        }

        struct numberedposition
        {
            public ushort num; public Vector3 pos;
            public override string ToString() { return num.ToString() + " => " + pos.ToString(); }
        }

        class vertexcomparer : IComparer<ushort>
        {
            numberedposition[] positions;

            public vertexcomparer(numberedposition[] possies)
            {
                positions = possies;
            }

            public int Compare(ushort x, ushort y)
            {
                int result;
                result = positions[x].pos.X.CompareTo(positions[y].pos.X);
                if (result == 0)
                {
                    result = positions[x].pos.Y.CompareTo(positions[y].pos.Y);
                    if (result == 0)
                        result = positions[x].pos.Z.CompareTo(positions[y].pos.Z);
                }
                return result;
            }
        }

        public static void AppendAdjacency(byte[] vertexdata,
                                           int vertexoffset,
                                           int vertexbyteoffset,
                                           int vertexstride,
                                           int numvertices,
                                           ushort[] indices,
                                           int indexoffset,
                                           int numindices,
                                           out ushort[] adjacencies,
                                           out string report)
        {
            adjacencyreport adjrep = new adjacencyreport(0);
            // Extract vertex positions from vertexOffset up to vertexOffset + the largest index used in 
            // the index buffer into an array (positions).
            // Tag each element with its vertex array index - the tag will be replaced with the location
            // of the first vertex found with an identical position, as part of the process of identifying 
            // vertices with the same position for sorting out common edges.
            // Can assume that there is no index used that is too large for a ushort
            // I am also assuming that indices are positive (can't find any doc on that)
            int maxvi = 0, minvi = numvertices;
            for (int i = indexoffset; i < indexoffset + numindices; i++)
            {
                if (indices[i] > maxvi) maxvi = indices[i];
                if (indices[i] < minvi) minvi = indices[i];
            }
            int firstvi = vertexoffset + minvi, numusedvertices = maxvi - minvi + 1, lostvertices = 0;
            numberedposition[] positions = new numberedposition[numusedvertices];
            {
                ushort[] vertexindices = new ushort[numusedvertices];
                for (int v = 0, vi = firstvi * vertexstride + vertexbyteoffset; v < numusedvertices; v++, vi += vertexstride)
                {
                    positions[v].num = (ushort)v;
                    positions[v].pos.X = BitConverter.ToSingle(vertexdata, vi);
                    positions[v].pos.Y = BitConverter.ToSingle(vertexdata, vi + 4);
                    positions[v].pos.Z = BitConverter.ToSingle(vertexdata, vi + 8);
                    vertexindices[v] = (ushort)v;
                }

                // Sort the set of vertex indices to order the vertices.  The ordering
                // is arbitrary - but will bring together identical positions.  Use this
                // ordering to identify sets of vertices with the same position.  Set the
                // number in the position array to the first member of the position group
                vertexcomparer comparer = new vertexcomparer(positions);
                Array.Sort<ushort>(vertexindices, comparer);
                for (int v = 1; v < vertexindices.Length; v++)
                {
                    if (comparer.Compare(vertexindices[v - 1], vertexindices[v]) == 0)
                    {
                        positions[vertexindices[v]].num = positions[vertexindices[v - 1]].num;
                        lostvertices++;
                    }
                }
            }

            // Make a list of edges, each with first and last vertex and
            // a space for adjacency value.  Note that each edge should end
            // up being entered twice - going each way
            // For quick access, all the edges starting with a given vertex
            // are linked from the index of the starting vertex (-offset).  
            // As a number of vertex indices are not used, this will lead 
            // to 'lostvertices' unused starter locations, so the edge
            // array is that much bigger.  It needs integer indexing
            //int ne = numusedvertices + lostvertices;
            edge[] edges = new edge[numindices + lostvertices];
            int next = (ushort)numusedvertices;
            for (int e = 0; e < next; e++) edges[e].other = -1;

            for (int i = indexoffset; i < indexoffset + numindices; i += 3)
            {
                for (int j = 0; j < 3; j++)
                {
                    int a = positions[indices[i + j] - minvi].num;
                    int b = positions[indices[i + (j + 1) % 3] - minvi].num;
                    int entry;
                    entry = a;
                    for (; ; )
                    {
                        if (edges[entry].other < 0)
                        {
                            edges[entry].other = b;
                            edges[entry].adj = -1;
                            edges[entry].link = -1;
                            break;
                        }
                        if (edges[entry].other == b)
                        {
                            adjrep.coincidentline++;
                            break;
                        }
                        if (edges[entry].link < 0)
                        {
                            edges[entry].link = next;
                            edges[next].other = b;
                            edges[next].adj = -1;
                            edges[next].link = -1;
                            entry = next;
                            next++;
                            break;
                        }
                        entry = edges[entry].link;
                    }
                }
            }

            if (next != edges.Length)
            {
                adjrep.vertexnotonedge += (edges.Length - next);
            }

            // Pass through the structure inserting adjacencies
            for (int i = indexoffset; i < indexoffset + numindices; i += 3)
            {
                for (int j = 0; j < 3; j++)
                {
                    int a = positions[indices[i + j] - minvi].num;
                    int b = positions[indices[i + (j + 1) % 3] - minvi].num;
                    int c = indices[i + (j + 2) % 3];
                    int entry = b;
                    for (; ; )
                    {
                        if (entry < 0)
                        {
                            adjrep.noadjacency++;
                            break;
                        }
                        if (edges[entry].other == a)
                        {
                            if (edges[entry].adj >= 0)
                            {
                                adjrep.doublefilled++;
                                break;
                            }
                            edges[entry].adj = c;
                            break;
                        }
                        entry = edges[entry].link;
                    }
                }
            }

            // Allocate and fill the adjacency index list
            int ad, at, other, adj;
            adjacencies = new ushort[numindices * 2];
            ad = 0;
            for (int i = indexoffset; i < indexoffset + numindices; i += 3)
            {
                for (int j = 0; j < 3; j++)
                {
                    adjacencies[ad++] = indices[i + j];               // vertex
                    at = positions[indices[i + j] - minvi].num;       // vertex to next vertex adjacency
                    other = positions[indices[i + (j + 1) % 3] - minvi].num;
                    for (; ; )
                    {
                        if (at < 0)
                        {
                            adjacencies[ad++] = (ushort)minvi;
                            break;
                        }
                        else if (edges[at].other == other)
                        {
                            adj = edges[at].adj;
                            if (adj >= 0)
                                adjacencies[ad++] = (ushort)adj;
                            else
                                adjacencies[ad++] = (ushort)minvi;
                            break;
                        }
                        at = edges[at].link;
                    }
                }
            }

            report = adjrep.ToString();
        }
    }
}
